package com.simon.study.algorithm.tree;

import com.alibaba.fastjson.JSON;
import com.alibaba.fastjson.JSONObject;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;


public class TreeTraversal {

    /** depth first search, also known as pre-order traversal*/
    public static void preorder(TNode node){
        if(node == null){ return; }

        System.out.println(node);

        if(node.left  != null){ preorder(node.left);  }
        if(node.right != null){ preorder(node.right); }
    }



    /** dfs, like the pre-order */
    public static void dfs(TNode node){
        if(node == null){ return; }

        Deque<TNode> queue = new ArrayDeque<>();
        queue.push(node);

        while (!queue.isEmpty()){
            TNode cur = queue.pop();

            queue.push(cur.right);
            queue.push(cur.left);
        }
    }

    public static void main(String[] args) {
        String txt = "{\"code\":1,\"name\":\"x1\",\"subList\":[{\"code\":11,\"name\":\"x11\",\"subList\":[{\"code\":111,\"name\":\"x111\",\"subList\":[{\"code\":1111,\"name\":\"x1111\"},{\"code\":1112,\"name\":\"x1112\"},{\"code\":1113,\"name\":\"x1113\"}]},{\"code\":112,\"name\":\"x112\",\"subList\":[{\"code\":1121,\"name\":\"xxx21\"},{\"code\":1122,\"name\":\"xxx22\"},{\"code\":1123,\"name\":\"xxx23\"}]},{\"code\":113,\"name\":\"xxx1\",\"subList\":[{\"code\":1131,\"name\":\"xxxx1\"},{\"code\":1132,\"name\":\"xxxx2\"},{\"code\":1133,\"name\":\"xxxx3\"}]}]},{\"code\":12,\"name\":\"x12\",\"subList\":[{\"code\":121,\"name\":\"x121\",\"subList\":[{\"code\":1211,\"name\":\"x1111\"},{\"code\":1212,\"name\":\"xxxx2\"},{\"code\":1213,\"name\":\"xxxx3\"}]},{\"code\":122,\"name\":\"x122\",\"subList\":[{\"code\":1221,\"name\":\"x1221\"},{\"code\":1222,\"name\":\"x1222\"},{\"code\":1223,\"name\":\"x1223\"}]},{\"code\":123,\"name\":\"x123\",\"subList\":[{\"code\":1231,\"name\":\"x1231\"},{\"code\":1232,\"name\":\"x1232\"},{\"code\":1233,\"name\":\"x1233\"}]}]}]}";
        JSONObject node = JSON.parseObject(txt);

        bfsExtend(node);
    }

    public static void bfsExtend(JSONObject node){
        List<Deque<JSONObject>>  all = new ArrayList<>();
        String name = "subList";

        Deque<JSONObject> cp = new ArrayDeque<>(), cs = new ArrayDeque<>(), ct = new ArrayDeque<>();
        cp.add(node);

        while (!cp.isEmpty()){
            JSONObject jp = cp.pop();
            ct.push(jp);

            List<Object> array = jp.getJSONArray(name);
            if(array != null && array.size() > 0) {
                for (Object son : array) {
                    JSONObject json = (JSONObject) son;
                    json.put("parent", jp.getString("code"));
                    cs.addLast(json);
                }
                jp.remove(name);
            }

            if(cp.isEmpty()){
                all.add( ct ); ct = new ArrayDeque<>();
                cp = cs; cs = new ArrayDeque<>();
            }
        }
        System.out.println(all);
    }



    /** breath first search / level first search */
    public static void bfs(TNode root){
        Deque<TNode> queue = new ArrayDeque<>();
        queue.addFirst(root);

        while (!queue.isEmpty()){
            TNode node = queue.pollFirst();

            // do sth.

            if( node.getLeft()  != null ){ queue.addLast( node.getLeft() );  }
            if( node.getRight() != null ){ queue.addLast( node.getRight() ); }

            // do sth. visit node
            System.out.println(node.getData());
        }
    }

    public static void inorder(TNode node){
        if(node == null){ return; }

        if(node.left  != node){ inorder(node.left); }
        System.out.println(node);
        if(node.right != null){ inorder(node.right); }
    }

    public static void inorderByLoop(TNode root){
        TNode node = root;

        Deque<TNode> stack = new ArrayDeque<>();
        while (node != null || !stack.isEmpty()){
            while (node != null){
                stack.push(node);
                // do sth. trun to pre-order
                node = node.getLeft();
            }

            if(!stack.isEmpty()){
                node = stack.pop();
                // do sth. here in-order
                System.out.println(node);
                node = node.getRight();
            }
        }
    }

    public static void inorderByLoop2(TNode root){
        TNode node = root;
        Deque<TNode> stack = new ArrayDeque<>();
        while (node != null || !stack.isEmpty()){
            if( node != null ){
                stack.push(node);
                node = node.getLeft();
            }else{
                node = stack.pop();System.out.println(node);
                node = node.getRight();
            }
        }
    }


    public static void postorder(TNode node){
        if(node == null){ return; }

        if(node.left  != node){ postorder(node.left);  }
        if(node.right != node){ postorder(node.right); }

        System.out.println(node);
    }


    public static void postorderByLoop(TNode root){
        TNode node = root, mark = null;
        Deque<TNode> stack = new ArrayDeque<>();

        while (node != null || !stack.isEmpty()){
            if(node != null){
                stack.push(node);
                node = node.getLeft();
            } else {
                node = stack.peekFirst();
                if(node.getRight() != null  && node.getRight() != mark){
                    node = node.getRight();
                }else{
                    node = stack.pop();
                    // do sth...
                    System.out.println(node);

                    mark = node;
                    node = null;
                }
            }
        }
    }
}
